package utils;

import common.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 自定义二叉树工具类
 */
public class TreeNodeUtil {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{3,5,1,6,2,0,8,null,null,7,4};
        TreeNode tree = transferArrToTreeByDiGui(arr);
        System.out.println(getHigh(tree));
        printTreeNode(tree);
    }

    /**
     * 通过队列的方式将数组转换为二叉树
     * @param arr
     * @return
     */
    public static TreeNode transferArrToTreeByQueue(Integer[] arr){
        if(arr == null || arr.length == 0 || arr[0] == null)  return null;
        Queue<TreeNode> queue = new ArrayDeque<>();
        TreeNode root = new TreeNode(arr[0]);
        queue.offer(root);
        int index = 1;
        TreeNode temp = null;
        while(!queue.isEmpty() && index < arr.length){
            temp = queue.poll();
            if(arr[index] != null){
                temp.left = new TreeNode(arr[index]);
                queue.offer(temp.left);
            }
            index++;
            if(index > arr.length)  break;
            if(arr[index] != null){
                temp.right = new TreeNode(arr[index]);
                queue.offer(temp.right);
            }
            index++;
        }
        return root;
    }

    //----------------------------------------------------------------------------
    /**
     * 将数组转换为二叉树，用递归实现。
     * 主要规律，二叉树中一个节点的下标为n，那么其左孩子就是2*n+1，右孩子为2*n+2
     * @param arr
     * @return
     */
    //方式一：ai
    public static TreeNode transferArrToTreeByDiGui(Integer[] arr){
        return build(arr,0);    //从根节点0索引开始
    }

    public static TreeNode build(Integer[] arr,int index){
        if(index >= arr.length || arr[index] == null)   return null;
        TreeNode now = new TreeNode(arr[index]);
        now.left = build(arr,index * 2 + 1);
        now.right = build(arr,index * 2 + 2);
        return now;
    }

    //方式二：自己写的递归
    public static TreeNode transferArrToTreeByDiGuiLonely(Integer[] arr){
        if(arr == null || arr.length == 0 || arr[0] == null)  return null;
        TreeNode root = new TreeNode(arr[0]);
        buildLonely(root,arr,0);
        return root;
    }

    public static void buildLonely(TreeNode root,Integer[] arr,int n){
        if(2 * n + 1 < arr.length && arr[2 * n + 1] != null){
            root.left = new TreeNode(arr[2 * n + 1]);
            buildLonely(root.left,arr,2 * n + 1);
        }
        if(2 * n + 2 < arr.length && arr[2 * n + 2] != null){
            root.right = new TreeNode(arr[2 * n + 2]);
            buildLonely(root.right,arr,2 * n + 2);
        }
    }
    //----------------------------------------------------------------------------

    /**
     * 获取二叉树的高度
     * @param root
     * @return
     */
    public static int getHigh(TreeNode root){
        if(root == null)    return 0;
        int left = getHigh(root.left);
        int right = getHigh(root.right);
        return left > right ? left + 1 : right + 1;
    }

    /**
     * 按层级打印二叉树
     * @param root
     */
    public static void printTreeNode(TreeNode root){
        if(root == null){
            System.out.println("当前二叉树为空，不能打印");
            return;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        TreeNode temp = null;
        while(!queue.isEmpty()){
            temp = queue.poll();
            System.out.print(temp.val + "  ");
            if(temp.left != null){
                queue.offer(temp.left);
            }
            if(temp.right != null){
                queue.offer(temp.right);
            }
        }
    }
}
